import heapq


class GraphAlgorithms:
    @staticmethod
    def dijkstra(graph, start):
        """
        Dijkstra算法（Dijkstra's Algorithm）用于求解单源最短路径问题。

        参数：
        graph (Dict[str, Dict[str, int]]): 加权有向图的邻接表表示，字典的键为节点名称，值为字典，表示该节点可达的邻接节点及其权重。
        start (str): 起始节点。

        返回：
        Dict[str, int]: 源节点到每个节点的最短路径长度。

        实现思路：
        1. 初始化距离字典dist，将起始节点距离设置为0，其余节点距离设置为正无穷大。
        2. 初始化优先队列queue，将起始节点和距离入队。
        3. 循环直到优先队列为空：
           - 出队一个节点和其距离。
           - 遍历该节点的邻接节点：
             - 如果经过当前节点到达邻接节点的距离更短，更新邻接节点的距离，并将邻接节点和新的距离入队。
        4. 返回最短路径长度字典dist。

        """

        # 初始化距离字典，起始节点距离为0，其他节点距离为正无穷大
        dist = {node: float('inf') for node in graph}
        dist[start] = 0

        # 初始化优先队列，起始节点和距离入队
        queue = [(0, start)]

        while queue:
            # 1. 出队一个节点和其距离
            curr_dist, curr_node = heapq.heappop(queue)

            # 如果当前节点的距离大于已计算的最短路径长度，跳过
            if curr_dist > dist[curr_node]:
                continue

            # 2. 遍历当前节点的邻接节点
            for neighbor, weight in graph[curr_node].items():
                new_dist = curr_dist + weight
                if new_dist < dist[neighbor]:
                    # 3. 更新邻接节点的距离，并将其入队
                    dist[neighbor] = new_dist
                    heapq.heappush(queue, (new_dist, neighbor))

        return dist

    @staticmethod
    def floyd_warshall(graph):
        """
        Floyd-Warshall算法（Floyd-Warshall Algorithm）用于求解所有节点间的最短路径。

        参数：
        graph (Dict[str, Dict[str, int]]): 加权有向图的邻接矩阵表示，字典的键为节点名称，值为字典，表示该节点可达的邻接节点及其权重。

        返回：
        Dict[str, Dict[str, int]]: 所有节点之间的最短路径长度。

        实现思路：
        1. 初始化距离字典dist，将已知路径的距离记录为邻接矩阵中的权重值，将其他路径的距离设置为正无穷大。
        2. 遍历所有节点对作为中间节点：
           - 遍历所有节点对作为起始节点：
             - 遍历所有节点对作为终止节点：
               - 如果经过中间节点的路径距离更短，更新路径距离。
        3. 返回最短路径长度字典dist。

        """

        nodes = list(graph.keys())
        num_nodes = len(nodes)

        # 1. 初始化距离字典，已知路径的距离为邻接矩阵中的权重值，其他路径的距离为正无穷大
        dist = {u: {v: graph[u][v] if u != v else 0 for v in nodes} for u in nodes}

        for k in nodes:
            for i in nodes:
                for j in nodes:
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        # 2. 经过中间节点的路径距离更短，更新路径距离
                        dist[i][j] = dist[i][k] + dist[k][j]

        return dist

    @staticmethod
    def prim(graph):
        """
        Prim算法（Prim's Algorithm）用于求解最小生成树问题。

        参数：
        graph (Dict[str, Dict[str, int]]): 加权无向图的邻接表表示，字典的键为节点名称，值为字典，表示该节点可达的邻接节点及其权重。

        返回：
        List[Tuple[str, str]]: 最小生成树的边列表。

        实现思路：
        1. 初始化一个集合visited，用于存储已访问的节点。
        2. 初始化一个最小堆heap，用于存储候选边，初始时将任意一个节点加入heap。
        3. 初始化一个边列表mst，用于存储最小生成树的边。
        4. 循环直到heap为空：
           - 1. 从heap中弹出权重最小的边(u, v)。
           - 2. 如果节点v未访问过，将边(u, v)加入mst，将节点v标记为已访问，将v的所有邻接边加入heap。
        5. 返回最小生成树的边列表mst。

        """

        visited = set()
        heap = []
        mst = []

        start_node = next(iter(graph))
        visited.add(start_node)

        for neighbor, weight in graph[start_node].items():
            heapq.heappush(heap, (weight, start_node, neighbor))

        while heap:
            # 4.1. 从heap中弹出权重最小的边(u, v)
            weight, u, v = heapq.heappop(heap)

            if v not in visited:
                # 4.2. 如果节点v未访问过，将边(u, v)加入mst
                visited.add(v)
                mst.append((u, v))

                for neighbor, weight in graph[v].items():
                    # 4.3. 将v的所有邻接边加入heap
                    heapq.heappush(heap, (weight, v, neighbor))

        return mst

    @staticmethod
    def kruskal(graph):
        """
        Kruskal算法（Kruskal's Algorithm）用于求解最小生成树问题。

        参数：
        graph (Dict[str, Dict[str, int]]): 加权无向图的邻接表表示，字典的键为节点名称，值为字典，表示该节点可达的邻接节点及其权重。

        返回：
        List[Tuple[str, str]]: 最小生成树的边列表。

        实现思路：
        1. 初始化一个边列表edges，将所有边加入edges。
        2. 将edges按权重从小到大排序。
        3. 初始化一个并查集，用于判断两个节点是否连通。
        4. 初始化一个边列表mst，用于存储最小生成树的边。
        5. 遍历排序后的边列表edges：
           - 5.1. 如果边(u, v)的两个节点不连通，则将边(u, v)加入mst，并将两个节点合并。
        6. 返回最小生成树的边列表mst。

        """

        edges = []
        for u, neighbors in graph.items():
            for v, weight in neighbors.items():
                edges.append((weight, u, v))
        edges.sort()

        parent = {node: node for node in graph}

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            parent[find(x)] = find(y)

        mst = []
        for weight, u, v in edges:
            # 5. 遍历排序后的边列表edges
            if find(u) != find(v):
                # 5.1. 如果边(u, v)的两个节点不连通
                union(u, v)
                mst.append((u, v))

        return mst

    @staticmethod
    def topological_sort(graph):
        """
        拓扑排序算法（Topological Sorting Algorithm）用于对有向无环图进行排序。

        参数：
        graph (Dict[str, List[str]]): 有向图的邻接表表示，字典的键为节点名称，值为节点可达的邻接节点列表。

        返回：
        List[str]: 拓扑排序后的节点列表。

        实现思路：
        1. 初始化一个栈stack，用于存储拓扑排序的节点。
        2. 初始化一个集合visited，用于存储已访问的节点。
        3. 对于图中的每个节点，调用dfs函数进行深度优先搜索：
           - 如果节点未访问过，递归访问其邻接节点。
        4. 将访问完的节点压入栈stack。
        5. 返回栈stack的逆序列表，即为拓扑排序后的节点列表。

        """

        def dfs(node):
            if node in visited:
                return

            visited.add(node)

            for neighbor in graph[node]:
                dfs(neighbor)

            stack.append(node)

        visited = set()
        stack = []

        for node in graph:
            dfs(node)

        return stack[::-1]

    @staticmethod
    def ford_fulkerson(graph, source, sink):
        """
        Ford-Fulkerson算法（Ford-Fulkerson Algorithm）用于求解最大流问题。

        参数：
        graph (List[List[int]]): 加权有向图的邻接矩阵表示，表示节点之间的容量。
        source (int): 源节点。
        sink (int): 汇点。

        返回：
        int: 最大流量。
        List[List[int]]: 最大流对应的流图的邻接矩阵表示。

        实现思路：
        1. 初始化流图，初始流量为0。
        2. 循环直到不存在增广路径：
           - 通过深度优先搜索寻找增广路径。
           - 如果找到增广路径，更新流图和流量。
        3. 返回最大流量和最大流对应的流图的邻接矩阵表示。

        """

        def dfs(node, flow):
            if node == sink:
                return flow

            visited.add(node)

            for neighbor, capacity in enumerate(graph[node]):
                if neighbor not in visited and capacity > 0:
                    new_flow = min(flow, capacity)
                    residual_capacity = dfs(neighbor, new_flow)

                    if residual_capacity > 0:
                        # 更新流图和流量
                        graph[node][neighbor] -= residual_capacity
                        graph[neighbor][node] += residual_capacity
                        return residual_capacity

            return 0

        num_nodes = len(graph)
        max_flow = 0

        while True:
            visited = set()
            flow = dfs(source, float('inf'))

            if flow == 0:
                break

            max_flow += flow

        return max_flow, graph

    @staticmethod
    def edmonds_karp(graph, source, sink):
        """
        Edmonds-Karp算法（Edmonds-Karp Algorithm）用于求解最大流问题。

        参数：
        graph (List[List[int]]): 加权有向图的邻接矩阵表示，表示节点之间的容量。
        source (int): 源节点。
        sink (int): 汇点。

        返回：
        int: 最大流量。
        List[List[int]]: 最大流对应的流图的邻接矩阵表示。

        实现思路：
        1. 初始化流图，初始流量为0。
        2. 循环直到不存在增广路径：
           - 通过广度优先搜索寻找增广路径。
           - 如果找到增广路径，更新流图和流量。
        3. 返回最大流量和最大流对应的流图的邻接矩阵表示。

        """

        def bfs():
            visited = [False] * num_nodes
            visited[source] = True
            parent = [-1] * num_nodes
            queue = [source]

            while queue:
                node = queue.pop(0)

                for neighbor, capacity in enumerate(graph[node]):
                    if not visited[neighbor] and capacity > 0:
                        visited[neighbor] = True
                        parent[neighbor] = node
                        queue.append(neighbor)

                        if neighbor == sink:
                            # 找到增广路径
                            return True, parent

            return False, parent

        num_nodes = len(graph)
        max_flow = 0

        while True:
            found_path, parent = bfs()

            if not found_path:
                break

            # 寻找增广路径上的最小容量
            path_flow = float('inf')
            node = sink
            while node != source:
                path_flow = min(path_flow, graph[parent[node]][node])
                node = parent[node]

            # 更新流图和流量
            node = sink
            while node != source:
                prev_node = parent[node]
                graph[prev_node][node] -= path_flow
                graph[node][prev_node] += path_flow
                node = prev_node

            max_flow += path_flow

        return max_flow, graph
if __name__ == '__main__':

    # 示例使用最短路径算法
    graph_dijkstra = {
        'A': {'B': 2, 'C': 5},
        'B': {'C': 1, 'D': 2},
        'C': {'D': 4},
        'D': {}
    }

    graph_floyd_warshall = {
        'A': {'A': 0, 'B': 2, 'C': float('inf'), 'D': float('inf')},
        'B': {'A': float('inf'), 'B': 0, 'C': 1, 'D': 2},
        'C': {'A': float('inf'), 'B': float('inf'), 'C': 0, 'D': 4},
        'D': {'A': float('inf'), 'B': float('inf'), 'C': float('inf'), 'D': 0}
    }

    graph_prim = {
        'A': {'B': 2, 'C': 5},
        'B': {'A': 2, 'C': 1, 'D': 2},
        'C': {'A': 5, 'B': 1, 'D': 4},
        'D': {'B': 2, 'C': 4}
    }

    graph_kruskal = {
        'A': {'B': 2, 'C': 5},
        'B': {'A': 2, 'C': 1, 'D': 2},
        'C': {'A': 5, 'B': 1, 'D': 4},
        'D': {'B': 2, 'C': 4}
    }

    graph_topological_sort = {
        'A': ['B', 'C'],
        'B': ['C', 'D'],
        'C': ['D'],
        'D': []
    }

    graph_ford_fulkerson = [
        [0, 16, 13, 0, 0, 0],
        [0, 0, 10, 12, 0, 0],
        [0, 4, 0, 0, 14, 0],
        [0, 0, 9, 0, 0, 20],
        [0, 0, 0, 7, 0, 4],
        [0, 0, 0, 0, 0, 0]
    ]

    graph_edmonds_karp = [
        [0, 16, 13, 0, 0, 0],
        [0, 0, 10, 12, 0, 0],
        [0, 4, 0, 0, 14, 0],
        [0, 0, 9, 0, 0, 20],
        [0, 0, 0, 7, 0, 4],
        [0, 0, 0, 0, 0, 0]
    ]

    graph_algo = GraphAlgorithms()

    # 示例调用最短路径算法（Dijkstra算法）
    start_node = 'A'
    shortest_paths_dijkstra = graph_algo.dijkstra(graph_dijkstra, start_node)
    print("最短路径长度字典(Dijkstra算法):", shortest_paths_dijkstra)
    """
    示例输出结果:
    最短路径长度字典(Dijkstra算法): {'A': 0, 'B': 2, 'C': 3, 'D': 5}
    """

    # 示例调用最短路径算法（Floyd-Warshall算法）
    shortest_paths_floyd_warshall = graph_algo.floyd_warshall(graph_floyd_warshall)
    print("所有节点之间的最短路径长度矩阵(Floyd-Warshall算法):", shortest_paths_floyd_warshall)
    """
    示例输出结果:
    所有节点之间的最短路径长度矩阵(Floyd-Warshall算法):
    {'A': {'A': 0, 'B': 2, 'C': 3, 'D': 5},
    'B': {'A': float('inf'), 'B': 0, 'C': 1, 'D': 2},
    'C': {'A': float('inf'), 'B': float('inf'), 'C': 0, 'D': 4},
    'D': {'A': float('inf'), 'B': float('inf'), 'C': float('inf'), 'D': 0}}
    """

    # 示例调用最小生成树算法（Prim算法）
    minimum_spanning_tree_prim = graph_algo.prim(graph_prim)
    print("最小生成树的边列表(Prim算法):", minimum_spanning_tree_prim)
    """
    示例输出结果:
    最小生成树的边列表(Prim算法): [('A', 'B'), ('B', 'C'), ('C', 'D')]
    """

    # 示例调用最小生成树算法（Kruskal算法）
    minimum_spanning_tree_kruskal = graph_algo.kruskal(graph_kruskal)
    print("最小生成树的边列表(Kruskal算法):", minimum_spanning_tree_kruskal)
    """
    示例输出结果:
    最小生成树的边列表(Kruskal算法): [('B', 'C'), ('A', 'B'), ('C', 'D')]
    """

    # 示例调用拓扑排序算法
    topological_order = graph_algo.topological_sort(graph_topological_sort)
    print("拓扑排序的节点列表:", topological_order)
    """
    示例输出结果:
    拓扑排序的节点列表: ['A', 'B', 'C', 'D']
    """

    # 示例调用最大流算法（Ford-Fulkerson算法）
    source_node = 0
    sink_node = 5
    max_flow, flow_graph = graph_algo.ford_fulkerson(graph_ford_fulkerson, source_node, sink_node)
    print("最大流量(Ford-Fulkerson算法):", max_flow)
    print("最大流对应的流图的邻接矩阵表示:")
    for i in range(len(flow_graph)):
        print(flow_graph[i])
    """
    示例输出结果:
    最大流量(Ford-Fulkerson算法): 23
    最大流对应的流图的邻接矩阵表示:
    [0, 12, 11, 0, 0, 0]
    [0, 0, 0, 11, 0, 0]
    [0, 1, 0, 0, 10, 0]
    [0, 0, 11, 0, 0, 12]
    [0, 0, 0, 0, 0, 7]
    [0, 0, 0, 0, 0, 0]
    """

    # 示例调用最大流算法（Edmonds-Karp算法）
    max_flow_ek, flow_graph_ek = graph_algo.edmonds_karp(graph_edmonds_karp, source_node, sink_node)
    print("最大流量(Edmonds-Karp算法):", max_flow_ek)
    print("最大流对应的流图的邻接矩阵表示:")
    for i in range(len(flow_graph_ek)):
        print(flow_graph_ek[i])
    """
    示例输出结果:
    最大流量(Edmonds-Karp算法): 23
    最大流对应的流图的邻接矩阵表示:
    [0, 12, 11, 0, 0, 0]
    [0, 0, 0, 11, 0, 0]
    [0, 1, 0, 0, 10, 0]
    [0, 0, 11, 0, 0, 12]
    [0, 0, 0, 0, 0, 7]
    [0, 0, 0, 0, 0, 0]
    """
